/*
 * @lc app=leetcode.cn id=LCR 152 lang=cpp
 * @lcpr version=30204
 *
 * [LCR 152] 验证二叉搜索树的后序遍历序列
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    bool traversal(vector<int> &postorder, int start, int end)
    {
        /* 递归终止条件 */
        if (start >= end)
            return true;
        int index = start;
        /* 中间处理逻辑 找到第一个大于根节点的下标*/
        while (postorder[index] < postorder[end])
            index++;
        /* 记录分割点 从这个点开始如果满足要求，那么左边的为左子树，右边的为右子树，最后一个为根节点*/
        int midIndex = index;
        // 这里在判断右子树是不是都满足大于根节点的要求
        while (postorder[index] > postorder[end])
            index++;
        /* 递归左右子树 */
        bool left = traversal(postorder, start, midIndex - 1);
        bool right = traversal(postorder, midIndex, end - 1);
        return index == end && left && right;
    }
    bool verifyTreeOrder(vector<int> &postorder)
    {
        // 方法一：递归
        // return traversal(postorder, 0, postorder.size() - 1);

        // 方法二：迭代
        stack<int> stk;
        int root = INT_MAX;
        // 反向遍历 根 右 左
        for (int i = postorder.size() - 1; i >= 0; i--)
        {
            if (postorder[i] > root)
                return false;
            // 当前节点值小于栈顶的值，说明该节点不是当前树的最右边路径的节点，回到大于当前节点的最小节点
            while (!stk.empty() && stk.top() > postorder[i])
            {
                root = stk.top();
                stk.pop();
            }
            // 每棵树的最右边路径节点都是递增的 因此入栈
            stk.push(postorder[i]);
        }
        return true;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [4,9,6,5,8]\n
// @lcpr case=end

// @lcpr case=start
// [4,6,5,9,8]\n
// @lcpr case=end

 */
